# 变化的多重背包问题

class SubItem:
    def __init__(self) -> None:
        self.price = 0
        self.importance = 0
        self.confidence = 0

    def update(self, price, importance):
        self.price = price
        self.importance = importance
        self.confidence = price*importance


class MainItem(SubItem):
    def __init__(self) -> None:
        super().__init__()
        self.isSubItem = False
        self.subItems = []


def getGroups(item: MainItem):
    '''
    返回多重背包中dp[j]的组合情况
    ans = {'items': [...], 'price': [...], 'confidence': [...]}
    '''
    ans = {'items': [], 'price': [], 'confidence': []}

    ans['price'].append(item.price)
    ans['confidence'].append(item.confidence)
    ans['items'].append([item])

    if len(item.subItems) == 1:
        price = item.price + item.subItems[0].price
        confidence = item.confidence + item.subItems[0].confidence
        ans['price'].append(price)
        ans['confidence'].append(confidence)
        ans['items'].append([item, item.subItems[0]])

    elif len(item.subItems) == 2:
        price = item.price + item.subItems[0].price
        confidence = item.confidence + item.subItems[0].confidence
        ans['price'].append(price)
        ans['confidence'].append(confidence)
        ans['items'].append([item, item.subItems[0]])

        price = item.price + item.subItems[1].price
        confidence = item.confidence + item.subItems[1].confidence
        ans['price'].append(price)
        ans['confidence'].append(confidence)
        ans['items'].append([item, item.subItems[1]])

        price = price + item.subItems[0].price
        confidence = confidence + item.subItems[0].confidence
        ans['price'].append(price)
        ans['confidence'].append(confidence)
        ans['items'].append([item,
                             item.subItems[0],
                             item.subItems[1]])

    return ans


# 输入
money, numItems = map(int, input().split())
money = int(money/10)
contents = [None]*numItems
tag = [0]*numItems
for i in range(numItems):
    price, importance, mainIndex = map(int, input().split())
    price = int(price/10)
    if mainIndex == 0:
        item = MainItem()
        item.update(price, importance)
    else:
        item = SubItem()
        item.update(price, importance)
    contents[i] = item
    tag[i] = mainIndex

# 将subitem纳入mainitem，并从contents中删除
for i in range(numItems):
    if tag[i]:
        contents[tag[i]-1].subItems.append(contents[i])

delCnt = 0
for i in range(numItems):
    if tag[i]:
        contents.__delitem__(i - delCnt)
        delCnt += 1


# 动态规划
dp = [0]*(money+1)
for item in contents:
    for i in range(money, -1, -1):
        groups = getGroups(item)
        for j in range(len(groups['price'])):
            items = groups['items'][j]
            price = groups['price'][j]
            confidence = groups['confidence'][j]
            if i < price:
                continue
            tmp = dp[i-price] + confidence
            dp[i] = max(dp[i], tmp)

print(dp[money]*10)
